package niuke;

/**
 * description:
 * author:zt
 * date:2021-08-12
 */

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * 请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
 */
public class NC136 {
    Map<Integer,Integer> map = new HashMap<>();
    List<Integer> res = new ArrayList<>();
    public int[] solve (int[] xianxu, int[] zhongxu) {
        // write code here
        for (int i = 0; i < zhongxu.length; i++) {
            map.put(zhongxu[i],i);
        }
        TreeNode root = recover(xianxu, 0, 0, zhongxu.length - 1);
        dfs(root,0);
        int[] ans = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    public TreeNode recover(int[] xianxu,int pos,int left,int right){
        if (left>right) return null;
        int ro = xianxu[pos];
        int index = map.get(ro);
        TreeNode root = new TreeNode(ro);
        root.left = recover(xianxu,pos+1,left,index-1);
        root.right = recover(xianxu,pos+index-left+1,index+1,right);

        return root;
    }
    public void dfs(TreeNode root, int depth){
        if (root==null) return;

        if (depth==res.size()) res.add(root.val);
        depth++;
        dfs(root.right,depth);
        dfs(root.left,depth);
    }
}
